package distanciaedicion;

import java.util.*;

public class AlgoritmoDistanciaEdicion {
	private static final Integer MAX = 999999;
	private ArrayList<Integer> costos;
	private ArrayList<ArrayList<Distancia>> distancias = null;
	private StringBuffer cadenaFuente;	
	private StringBuffer cadenaDestino;
	private StringBuffer cadenaAuxiliar;
	
	private void resetDistancias() {
		for(Integer i = 0; i < distancias.size();++i)
			for(Integer j = 0; j< distancias.get(i).size(); ++j) 
				distancias.get(i).get(j).setCostoActual(0);			
	}
	
    private static Distancia distanciaMinima(Integer costoCopiar, Integer costoInsertar,
    		Integer costoIntercambiar, Integer costoReemplazar, 
    		Integer costoBorrar
    		, Integer costoTerminar) {
       Operacion operacion = null;
       Distancia distancia = null;
    	if ((costoCopiar <= costoInsertar)&&(costoCopiar <= costoIntercambiar)
        		&&(costoCopiar <= costoReemplazar)&&
        		(costoCopiar <= costoBorrar)&&(costoCopiar <= costoTerminar))
    			operacion = Copiar.getInstance();    	
   		if ((costoInsertar <= costoCopiar)&&(costoInsertar <= costoIntercambiar)
           		&&(costoInsertar <= costoReemplazar)&&
           		(costoInsertar <= costoBorrar)&&(costoInsertar <= costoTerminar)) 
       			operacion = Insertar.getInstance();
       	if ((costoIntercambiar <= costoCopiar)&&(costoIntercambiar<= costoInsertar)
           		&&(costoIntercambiar <= costoReemplazar)&&
           		(costoIntercambiar <= costoBorrar)&&(costoIntercambiar <= costoTerminar)) 
        		operacion = Intercambiar.getInstance();
    	
       	if ((costoReemplazar <= costoCopiar)&&(costoReemplazar <= costoIntercambiar)
        		&&(costoReemplazar <= costoInsertar)&&
        		(costoCopiar <= costoBorrar)&&(costoCopiar <= costoTerminar)) 
       			operacion = Reemplazar.getInstance();
       	
       	if ((costoBorrar <= costoInsertar)&&(costoBorrar <= costoIntercambiar)
        		&&(costoBorrar <= costoReemplazar)&&
        		(costoBorrar <= costoCopiar)&&(costoBorrar <= costoTerminar)) 
       			operacion = Borrar.getInstance();
       	else 	operacion = Terminar.getInstance();
    	
        distancia = new Distancia(operacion);
        return distancia;    	
    }
    
    private static Integer max(Integer a, Integer b) {
    	if(a <= b) return b;
    	return a;
    }
 
    public AlgoritmoDistanciaEdicion(StringBuffer cadenaFuente, StringBuffer cadenaDestino,
			ArrayList<Integer> costos) {
		this.costos = costos;
		this.cadenaFuente = cadenaFuente;
		this.cadenaDestino = cadenaDestino;
		cadenaAuxiliar = new StringBuffer(max(cadenaFuente.length(),cadenaDestino.length()));
		
		distancias = new ArrayList<ArrayList<Distancia>>(cadenaFuente.length() + 1);
		for (Integer index = 0; index < distancias.size(); ++index) 
			distancias.add(index, new ArrayList<Distancia>(cadenaDestino.length() + 1));
	resetDistancias();	
	}
  
    private void inicializarOperaciones() {
    	Insertar.getInstance().setCosto(costos.get(Settings.INDICE_COSTO_INSERCION));
    	Borrar.getInstance().setCosto(costos.get(Settings.INDICE_COSTO_BORRADO));
    	Reemplazar.getInstance().setCosto(costos.get(Settings.INDICE_COSTO_REEMPLAZAR));
    	Copiar.getInstance().setCosto(costos.get(Settings.INDICE_COSTO_COPIAR));
    	Intercambiar.getInstance().setCosto(costos.get(Settings.INDICE_COSTO_INTERCAMBIAR));
    	Terminar.getInstance().setCosto(costos.get(Settings.INDICE_COSTO_TERMINAR));
    	
    }
    public Integer calcularDistancias() {
    	inicializarOperaciones();
    	for(int i = 0;i < cadenaFuente.length() + 1;i++) {
    		Borrar borrar = Borrar.getInstance();
    		Distancia distancia = new Distancia(borrar);
    		distancia.setCostoActual(i);
    		distancias.get(i).add(0, distancia);
    	}
    	for(int j = 1;j < cadenaDestino.length() + 1  ;j++)  {
    		Borrar borrar = Borrar.getInstance();
    		Distancia distancia = new Distancia(borrar);
    		distancia.setCostoActual(j);
    		distancias.get(0).add(j, distancia);
    	}
    	for(Integer i = 1; i < cadenaFuente.length() + 1 ;++i) {
    		for(Integer j = 1;j < cadenaDestino.length() + 1 ;++j) { 
    			// si el siguiente caracter x[i - 1] == y[j - 1] copio el caracter de
    			// x a z 
    			// de lo contrario el costo es maximo y no se realiza la operacion
    			Integer costoCopiar = distancias.get(i - 1).get(j - 1).getCostoActual() +
    					((cadenaFuente.charAt(i - 1) == 
    					cadenaFuente.charAt(j - 1))?1:0)*Copiar.getInstance().getCosto() +
    					((cadenaFuente.charAt(i - 1) == 
    					cadenaFuente.charAt(j - 1))?0:1) * MAX;  
    			
    			Integer costoInsertar = distancias.get(i).get(j - 1).getCostoActual() +
    					Insertar.getInstance().getCosto();
    			// solo intercambio x[i -1] y x[i] si x[i] = y[j -1] ey x[i - 1] = x[j]
    			// de lo contrario el costo es maximo y no se realiza la operacion
    			Integer costoIntercambiar = distancias.get(i - 1).get(j - 1).getCostoActual() +
    					(((cadenaFuente.charAt(i - 1) == cadenaDestino.charAt(j)) &&
    							(cadenaFuente.charAt(i) == cadenaFuente.charAt(j - 1)))?1:0) * 
    							Intercambiar.getInstance().getCosto() + 
    							(((cadenaFuente.charAt(i - 1) == cadenaDestino.charAt(j)) &&
    							(cadenaFuente.charAt(i) == cadenaFuente.charAt(j - 1)))?0:1)* MAX;
    			
    			Integer costoReemplazar = distancias.get(i - 1).get(j - 1).getCostoActual() +
    					Reemplazar.getInstance().getCosto();
    			
    			Integer costoBorrar = distancias.get(i).get(j).getCostoActual() + 
    					Borrar.getInstance().getCosto();
    			// solo ejecuto terminar si z contiene todos los caracteres de y
    			// de lo contrario el costo es maximo y no se realiza la operacion
    			Integer costoTerminar = distancias.get(i - 1).get(j - 1).getCostoActual() +
    					((j == cadenaDestino.length())?1:0)*Terminar.getInstance().getCosto() +
    					((j == cadenaDestino.length())?1:0)*MAX;
    			Distancia distancia = distanciaMinima(costoCopiar, 
    					costoInsertar, costoIntercambiar, 
    					costoReemplazar, costoBorrar, costoTerminar);
    			distancia.setCaracterFuente(cadenaFuente.charAt(i));
    			distancia.setCaracterDestino(cadenaDestino.charAt(j));
    			distancias.get(i).add(j, distancia);
    		}
    	}
    return distancias.get(cadenaFuente.length()).get(cadenaDestino.length()).getCostoActual();
    }
    
    private LinkedList<Operacion> reconstruirSecuenciaOperaciones() {
    	Integer i = 1;
    	Integer j = 1;
    	LinkedList<Operacion> operaciones = new LinkedList<Operacion>();
    	Distancia distancia = distancias.get(i).get(j);
    	while( i < cadenaFuente.length()) {
    		while(j < cadenaDestino.length() ) {
    			if ((i + 1)==(i + distancias.get(i + 1).get(j + 1).getSentidoHorizontal())&&
    					((j + 1) == distancias.get(i + 1).get(j + 1).getSentidoVertical())) {
    				i++;
    				j++;
    			}
    			if ((i ==(i + distancias.get(i + 1).get(j + 1).getSentidoHorizontal())&&
    					((j + 1) == distancias.get(i + 1).get(j + 1).getSentidoVertical()))) {
    				j++;
    			}
    			if ((i + 1)==(i + distancias.get(i + 1).get(j + 1).getSentidoHorizontal())&&
    					((j == distancias.get(i + 1).get(j + 1).getSentidoVertical()))) {
    				i++;
    			}
    		operaciones.addLast(distancias.get(i).get(j).getOperacion());   				
    		}
    	}
    	return operaciones;
    }
    
    public void execute() {
    	Integer distanciaEdicion = calcularDistancias();
    	LinkedList<Operacion> operaciones = reconstruirSecuenciaOperaciones();
    	Iterator<Operacion> itOperaciones = operaciones.iterator();
    	while (itOperaciones.hasNext()) {
    		itOperaciones.next().execute();
    	}
    	System.out.println();
    	System.out.println(distanciaEdicion);
    }
}
